#ifndef __TDP2_HASHMAP_HPP__
#define __TDP2_HASHMAP_HPP__

#include <new>
#include "tdp2_hash.hpp"
#include "tdp2_vector.hpp"
#include "tdp2_copier.hpp"

namespace TDP
{
	namespace Containers
	{
		template<class Tk, class Tv> class HashMap;

		template<class Tk, class Tv>
		class HashMapIterator
		{
			LargeUInt _index;
			const HashMap<Tk,Tv> *_hashMap;
			bool _present;

		public:
			inline HashMapIterator()
			{
				_present = false;
			}

			inline HashMapIterator(const HashMap<Tk,Tv> *hashMap, LargeUInt index)
			{
				_hashMap = hashMap;
				_index = index;
				_present = true;
			}

			inline bool Present() const
			{
				return _present;
			}

			inline HashMapIterator Next() const
			{
				return _hashMap->Iterate(_index + 1);
			}

			inline const Tk &Key() const
			{
				return _hashMap->ElementKey(_index);
			}
		};

		template<class Tk, class Tv>
		class HashMap
		{
			struct HashElement
			{
				enum HashElementType
				{
					HMT_ElementTypeEmpty,			// Empty bucket, terminates probe
					HMT_ElementTypeDeleted,			// Empty bucket, won't terminate probe

					HMT_ContainsData,

					HMT_ElementTypeFilled,			// Bucket with a value
					HMT_ElementTypeLoose,			// Unsorted value
				};

				Tk key;
				Tv value;

				HashElementType elementType;
				UInt32 hash;
			};

			HashElement *_elements;
			LargeUInt _numElements;
			RDX::ObjectManagement::Allocator _alloc;
			UInt32 (*_hashFunc) (UInt32 hash, const Tk *ptr);
			LargeUInt _load;
			LargeUInt _loadFactorPercentage;

			inline void SwapEntries(LargeUInt index1, LargeUInt index2)
			{
				if(index1 == index2)
					return;

				UInt8 tempBytes[sizeof(HashElement)];
				memcpy(&tempBytes, _elements + index1, sizeof(HashElement));
				memcpy(_elements + index1, _elements + index2, sizeof(HashElement));
				memcpy(_elements + index2, &tempBytes, sizeof(HashElement));
			}

		public:
			// Returns the first match of a key.  If not found, returns an index that it can be inserted at
			inline LargeInt FindElementIndex(const Tk &key, UInt32 hash, bool &found) const
			{
				const HashElement *elements = _elements;

				if(!elements)
				{
					found = false;
					return 0;
				}

				LargeUInt numEntries = _numElements;
				LargeUInt idx = static_cast<LargeUInt>(hash) % static_cast<LargeUInt>(numEntries);

				LargeUInt insertableIndex = 0;
				bool hitInsertable = false;

				for(LargeUInt n=0;n<numEntries;n++,idx++)
				{
					if(idx == numEntries)
						idx = 0;

					const HashElement *entry = &_elements[idx];
					if(entry->elementType != HashElement::HMT_ElementTypeFilled)
					{
						if(hitInsertable == false)
						{
							hitInsertable = true;
							insertableIndex = idx;
						}
						
						if(entry->elementType == HashElement::HMT_ElementTypeEmpty)
							break;	// Entry doesn't exist

						if(entry->elementType == HashElement::HMT_ElementTypeDeleted)
							continue;	// Keep going
					}

					if(key == entry->key)
					{
						found = true;
						return idx;
					}
				}

				found = false;
				return insertableIndex;
			}

			inline void SetHashFunction(UInt32 (*hashFunc) (UInt32 hash, const Tk *ptr))
			{
				_hashFunc = hashFunc;
			}

			static inline UInt32 SimpleHashFunc(UInt32 hash, const Tk *ptr)
			{
				return TDP::Hash32(hash, ptr, sizeof(*ptr));
			}

			inline LargeUInt FindElementIndex(const Tk &key, bool &found, UInt32 *hashValue) const
			{
				UInt32 hash = _hashFunc(0, &key);

				if(hashValue)
					*hashValue = hash;

				return FindElementIndex(key, hash, found);
			}

			inline void DestroyEntry(LargeUInt idx)
			{
				HashElement *element = _elements[idx];
				element->key.~Tk();
				element->value.~Tv();
			}

			inline void RemoveEntry(LargeUInt idx)
			{
				HashElement *entry = _elements + idx;
				LargeInt numEntries = _numElements;

				if(entry->elementType == HashElement::HMT_ElementTypeFilled)
				{
					// If the next entry is empty, then this can be emptied, otherwise it needs to act as a gap filler for probing
					const HashElement *nextEntry = _elements + idx + 1;
					if(idx == numEntries - 1)
						nextEntry = _elements;
					
					DestroyEntry(idx);
					if(nextEntry->elementType == HashElement::HMT_ElementTypeEmpty)
						entry->elementType = HashElement::HMT_ElementTypeEmpty;
					else
						entry->elementType = HashElement::HMT_ElementTypeDeleted;
					load--;
				}
			}

			inline HashMap()
			{
				_load = 0;
				_loadFactorPercentage = 80;
				_elements = NULL;
				_numElements = 0;
				_alloc = TDP::Allocator::Default();
				_hashFunc = TDP::Hash32;
			}

			inline explicit HashMap(const RDX::ObjectManagement::Allocator &alloc)
			{
				_load = 0;
				_loadFactorPercentage = 80;
				_elements = NULL;
				_numElements = 0;
				_alloc = alloc;
				_hashFunc = SimpleHashFunc;
			}

			inline bool ContainsKey(const Tk &key) const
			{
				bool found;
				FindElementIndex(key, found, static_cast<HashValue *>(NULL));
				return found;
			}

			inline bool TrySetElement(const Tk &key, const Tv &value, UInt32 hashValue)
			{
				bool found;
				LargeUInt index = FindElementIndex(key, hashValue, found);

				if(!found)
					return false;
				_elements[index].value = value;
				return true;
			}
			
			inline void SetElement(const PanicHandler *ph, const Tk &key, const Tv &value, UInt32 hashValue)
			{
				if(!TrySetElement(key, value, hashValue))
					TDP::Panic(ph, FatalErrors::ERR_AllocationFailed);
			}

			inline bool TrySetElement(const Tk &key, const Tv &value)
			{
				bool found;
				LargeUInt index = FindElementIndex(key, found);

				if(!found)
					return false;
				_elements[index].value = value;
				return true;
			}
			
			inline void SetElement(const PanicHandler *ph, const Tk &key, const Tv &value)
			{
				if(!TrySetElement(key, value))
					TDP::Panic(ph, FatalErrors::ERR_AllocationFailed);
			}

			inline const Tv *TryGetElement(const Tk &key, UInt32 *hashValue) const
			{
				bool found;
				LargeUInt index = FindElementIndex(key, found, hashValue);

				if(!found)
					return NULL;
				return &_elements[index].value;
			}

			inline Tv *TryGetElement(const Tk &key, UInt32 *hashValue)
			{
				bool found;
				LargeUInt index = FindElementIndex(key, found, hashValue);

				if(!found)
					return NULL;
				return &_elements[index].value;
			}

			inline const Tv &GetElement(const PanicHandler *ph, const Tk &key, UInt32 *hashValue) const
			{
				const Tv *e = TryGetElement(key, hashValue);
				if(!e)
					TDP::Panic(ph, FatalErrors::ERR_ValueNotFound);
				return *e;
			}

			inline Tv &GetElement(const PanicHandler *ph, const Tk &key, UInt32 *hashValue)
			{
				const Tv *e = TryGetElement(key, hashValue);
				if(!e)
					TDP::Panic(ph, FatalErrors::ERR_ValueNotFound);
				return *e;
			}

			inline const Tv *TryGetElement(const Tk &key) const
			{
				return TryGetElement(key, static_cast<HashValue *>(NULL));
			}

			inline Tv *TryGetElement(const Tk &key)
			{
				return TryGetElement(key, static_cast<HashValue *>(NULL));
			}

			inline const Tv &GetElement(const PanicHandler *ph, const Tk &key) const
			{
				const Tv *e = TryGetElement(key);
				if(!e)
					TDP::Panic(ph, FatalErrors::ERR_ValueNotFound);
				return *e;
			}

			inline Tv &GetElement(const PanicHandler *ph, const Tk &key)
			{
				Tv *e = TryGetElement(key);
				if(!e)
					TDP::Panic(ph, FatalErrors::ERR_ValueNotFound);
				return *e;
			}


			// Attempts to resize the entry array, returns true if successful, false otherwise
			inline bool ResizeEntryArray(LargeUInt newCount)
			{
				HashElement *elements = _elements;
				LargeUInt oldCount;

				oldCount = _numElements;

				HashElement *newElements = _alloc.Realloc<HashElement>(elements, newCount);

				if(!newElements)
					return false;
				_numElements = newCount;

				_elements = newElements;

				for(LargeUInt i=oldCount ; i < newCount ; i++)
					_elements[i].elementType = HashElement::HMT_ElementTypeEmpty;

				return true;
			}

			inline Tv *TryInsert(const Tk &key, const Tv &value, UInt32 hash, typename Copier<Tk>::TrySetFunc keyCopyFunc = Copier<Tk>::SimpleTrySetFunc, typename Copier<Tv>::TrySetFunc valueCopyFunc = Copier<Tk>::SimpleTrySetFunc)
			{
				if(_load*100 >= _loadFactorPercentage*_numElements)
				{
					LargeUInt oldCount = _numElements;

					LargeUInt newCount;
					if(!oldCount)
						newCount = 2;
					else
						newCount = oldCount * 2;

					if(!ResizeEntryArray(newCount))
						return NULL;

					Rehash(oldCount, newCount);
				}

				bool found;
				LargeUInt index = FindElementIndex(key, hash, found);

				if(found)
				{
					_elements[index].value = value;
				}
				else
				{
					if(!keyCopyFunc(_elements[index].key, key))
						return NULL;

					try
					{
						if(!valueCopyFunc(_elements[index].value, value))
							return NULL;
					}
					catch(...)
					{
						_elements[index].key.~Tk();
						throw;
					}

					_elements[index].hash = hash;
					_elements[index].elementType = HashElement::HMT_ElementTypeFilled;

					_load++;
				}
				return &_elements[index].value;
			}

			inline Tv &Insert(const PanicHandler *ph, const Tk &key, const Tv &value, UInt32 hash)
			{
				Tv *v = TryInsert(key, value, hash);
				if(!v)
					TDP::Panic(ph, FatalErrors::ERR_AllocationFailed);
				return *v;
			}
			
			inline Tv *TryInsert(const Tk &key, const Tv &value, typename Copier<Tk>::TrySetFunc keyCopyFunc = Copier<Tk>::SimpleTrySetFunc, typename Copier<Tv>::TrySetFunc valueCopyFunc = Copier<Tv>::SimpleTrySetFunc)
			{
				UInt32 hash = _hashFunc(0, &key);

				return TryInsert(key, value, hash, keyCopyFunc, valueCopyFunc);
			}

			inline Tv &Insert(const PanicHandler *ph, const Tk &key, const Tv &value)
			{
				Tv *v = TryInsert(key, value);
				if(!v)
					TDP::Panic(ph, FatalErrors::ERR_AllocationFailed);
				return *v;
			}

			
			inline HashMapIterator<Tk,Tv> Iterate(LargeUInt index = 0)
			{
				if(!_elements)
					return HashMapIterator<Tk,Tv>();

				while(index < _numElements)
				{
					if(_elements[index].elementType > HMT_ContainsData)
						return HashMapIterator<Tk,Tv>(this, index);
				}
			}

			inline const Tk &ElementKey(LargeUInt index) const
			{
				return _elements[index].key;
			}

			inline const Tk &ElementValue(LargeUInt index) const
			{
				return _elements[index].value;
			}

			inline void Rehash(LargeUInt numBaseElements, LargeUInt numResultElements)
			{
				// Convert all deleted to empty and all filled to loose
				for(LargeUInt i=0;i<numBaseElements;i++)
				{
					HashElement *entry = _elements + i;

					if(entry->elementType == HashElement::HMT_ElementTypeDeleted)
						entry->elementType = HashElement::HMT_ElementTypeEmpty;
					else if(entry->elementType == HashElement::HMT_ElementTypeFilled)
						entry->elementType = HashElement::HMT_ElementTypeLoose;
				}

				LargeUInt largerCount = numBaseElements;
				if(numResultElements > largerCount)
					largerCount = numResultElements;

				for(LargeUInt i=0;i<largerCount;i++)
				{
					HashElement *element = _elements + i;

					// As long as this bucket contains a filled element, keep moving it to the proper location
					while(element->elementType == HashElement::HMT_ElementTypeLoose)
					{
						if(element->elementType == HashElement::HMT_ElementTypeEmpty)
							break;

						// Find a new location for this element
						LargeUInt destination = static_cast<LargeUInt>(element->hash) % numResultElements;
						while(_elements[destination].elementType == HashElement::HMT_ElementTypeFilled)
						{
							destination++;
							if(destination == numResultElements)
								destination = 0;
						}

						// Flag filled and swap with whatever's currently at the destination
						element->elementType = HashElement::HMT_ElementTypeFilled;
						SwapEntries(i, destination);
					}
				}
			}
		};
	}
}

#endif
